"""
试写一个算法：在一个M行N列的矩阵中，如果查找到一个元素为“0”，将其所
在的行和列的元素都设置为“0”

"""
# 空间复杂度 O(m+n)
def zero(matrix):
    m = [False] * len(matrix)
    n = [False] * len(matrix[0])

    # 先记录有0的行和列
    for i in range(len(m)):
        for j in range(len(n)):
            if matrix[i][j] == 0:
                m[i] = True
                n[j] = True
    
    # 如果元素所在行或者列有记录 则该元素置为0
    for i in range(len(m)):
        for j in range(len(n)):
            if(m[i] == True or n[j] == True):
                matrix[i][j] = 0

    # 打印
    for i in range(len(m)):
        print(matrix[i])

matrix = [  [ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 ],
            [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
            [ 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 ],
            [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
            [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]    

zero(matrix)